题目大意
有 个 A 类区间， 个 B 类区间，以及 。找到一组合法解 满足 ，使得令 A 类区间不超过 个有共同子区间、B 类区间有不超过 个有共同子区间，所需删除区间尽量小。设最小删除区间数为 ，输出 。保证所有区间左右端点互不相同，。
本博客包含一个错解和两个正解。
考场解法（错解）
考虑一组最优解 ，如果减小 的值，A 类区间就要删除更多的区间，B 类区间会减少需要删除的区间。但是因为 已经是最优解了，B 类区间减少的要删除的区间数量不大于 A 类区间要增加的区间数量。
因此推测最后的答案呈单峰性质。考虑三分查找找到峰值。
现在的问题就是我已经确定了 ，如何用一个可以接受的复杂度去求解需要删除多少个区间。不难看出，如果按照区间的左端点排个序，显然可以按照顺序，加进一个区间时，如果区间左端点上没有被至少 个区间覆盖，就加进去，否则删掉这个区间。用线段树维护区间的覆盖情况。
复杂度
错误的原因是，可以证明这并不是单峰的。
改题解法（正解）
既然并不是单峰的，那不就可以模拟退火吗？
朴素的贪心算法，我们找到一个点，每次贪心地走左边或者右边，如果当前这个点的函数值（即答案）更小就走这边。显然这是错误的，我们会卡死在一个局部最优的情况。这个贪心显然被假掉的原因就在于我们被拘束在一个局部凸包里面，无法跳出去。如果我们给一个概率使它可以跳出去呢？
这就是模拟退火有一定概率得到正确答案的原因。确切地说，考虑模拟物理降温的过程：
- 设定一个当前温度 。
- 设定每次温度的变化比 。
- 每次退火，找到一个向左的位置和向右的位置，求其函数值 。
- 如果一端比当前状态小的话，贪心地跳过去。
- 如果比当前状态大，我们有一定的概率跳过去。
- 温度降到一定值以下截止。
找到的向左的位置和向右的位置、以及跳上去的概率不能乱定。原则上，越到后面，我们会越趋近于正解，所以应该逐渐稳定下来。根据热力学物理学家们的研究，增量的概率最好为 ，其中 是当前解与当前目标解之差。
本着越来越稳定的原则，温度越低波动应该越小，因此一般以 为左右发展长度，其中 是根据题目不同自行设定的，一般直接设为 ， 是属于区间 的实数。
在本题中，因为洛谷数据较水，并不需要特别在意跳到劣解的概率，写好波动范围即可。
冥间数据 AC 代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int max_n=100005;
inline int read(){
int x=0;bool w=0;char c=getchar();
while(c<'0' || c>'9') w|=c=='-',c=getchar();
while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return w?-x:x;
}
inline void write(int x){
if(x<0) x=-x,putchar('-');
if(x>9) write(x/10);
putchar(x%10^48);
}
int n,m1,m2,q1[max_n*4],q2[max_n*4];
struct plane{
int l,r;
inline void init(int x,int y){
l=x,r=y;
}
}a[max_n],b[max_n];
inline bool cmp(plane a,plane b){
return a.l<b.l;
}
int lisan[max_n*4],cntls;
int ans,nowans,R1,R2;
int In[max_n],a1[max_n*4],a2[max_n*4],ar[max_n],br[max_n];
inline int check(int in){ // O(n) 判断多少个飞机停桥
if(In[in]) return In[in];
int out=n-in,res=0,tmp=0;
for(register int i=1;i<=R1;++i)
a1[i]=q1[i];
for(register int i=1;i<=R2;++i)
a2[i]=q2[i];
for(register int i=1;i<=R1;++i){
if(a1[i]==1 && tmp<in)
++res;
else if(a1[i]==1) // 满员了，删除这个飞机的信息
a1[i]=a1[ar[i]]=0;
tmp+=a1[i];
}
tmp=0;
for(register int i=1;i<=R2;++i){ // 国际航班同理
if(a2[i]==1 && tmp<out)
++res;
else if(a2[i]==1)
a2[i]=a2[br[i]]=0;
tmp+=a2[i];
}
return In[in]=res;
}
int As[max_n];
const int tim=1;
const double tem=0.98,delta=0.98,eps=0.0001;
inline void findans(){ // 模拟退火
int anss=ans,nowanss=nowans;
double nowt=tem;
while(nowt>eps){
int len=1.0*nowt*n*rand()/RAND_MAX,L=nowanss-len,R=nowanss+len;
if(L>=0){
int tmp=check(L);
if(tmp>anss){
anss=tmp,
nowanss=L;
if(ans<anss){
ans=anss,
nowans=nowanss;
}
}
}
if(R<=n){
int tmp=check(R);
if(tmp>anss){
anss=tmp,
nowanss=R;
if(ans<anss){
ans=anss,
nowans=nowanss;
}
}
}
nowt*=delta;
}
if(ans<anss){
ans=anss,
nowans=nowanss;
}
}
signed main(){
freopen("airport.in","r",stdin),
freopen("airport.out","w",stdout);
n=read(),m1=read(),m2=read();
for(register int i=1;i<=m1;++i){
int l=read(),r=read();
a[i].init(l,r);
lisan[++cntls]=l,
lisan[++cntls]=r;
}
sort(lisan+1,lisan+1+cntls),R1=cntls; // 离散化
for(register int i=1;i<=m1;++i){
a[i].l=lower_bound(lisan+1,lisan+1+cntls,a[i].l)-lisan;
a[i].r=lower_bound(lisan+1,lisan+1+cntls,a[i].r)-lisan;
q1[a[i].l]=1,q1[a[i].r]=-1;
ar[a[i].l]=a[i].r;
}
cntls=0;
for(register int i=1;i<=m2;++i){
int l=read(),r=read();
b[i].init(l,r);
lisan[++cntls]=l,
lisan[++cntls]=r;
}
sort(lisan+1,lisan+1+cntls),R2=cntls;
for(register int i=1;i<=m2;++i){
b[i].l=lower_bound(lisan+1,lisan+1+cntls,b[i].l)-lisan;
b[i].r=lower_bound(lisan+1,lisan+1+cntls,b[i].r)-lisan;
q2[b[i].l]=1,q2[b[i].r]=-1;
br[b[i].l]=b[i].r;
}
sort(a+1,a+1+m1,cmp), // 记得排序
sort(b+1,b+1+m2,cmp);
ans=check(n/2),nowans=n/2;
for(register int i=1;i<=tim;++i)
findans();
write(ans);
return 0;
}
